The present invention relates generally to information processing, and in particular to an apparatus and method for controlling link stack corruption during branching.
Modern high frequency microprocessors are typically deeply pipelined devices. For efficient instruction execution in such processors, instructions are often fetched and executed speculatively. An instruction may be fetched many cycles before it is executed. Since branch instructions may cause instruction fetching to start from a non-sequential location, the direction and target of a branch instruction is predicted when the branch is fetched so that instruction fetching can proceed from the most likely address. The prediction is compared with the actual direction and target of the branch instruction when the instruction is executed. If it is determined that the branch has been mispredicted (either its target or its direction), then the branch instruction is completed and all instructions fetched after the branch are flushed out of the instruction pipeline and new instructions are fetched either from the sequential path of the branch (if the branch is resolved as not taken) or from the target path of the branch (if the branch is resolved as taken).
Often there are a number of branches (i.e., subroutine calls and returns) between the instructions that are being fetched and the instructions that are being executed in the processor execution units. Therefore, to handle subroutine calls and returns efficiently, many high frequency microprocessors employ a link stack. On a subroutine call, the address of the following instruction is xe2x80x9cpushedxe2x80x9d into the stack while on a subroutine return, the contents at the top of the stack (which is expected to contain the address of the instruction following the original subroutine call) are xe2x80x9cpoppedxe2x80x9d from the stack. Since pushing and popping from a hardware stack can normally be done when the branch is fetched, which is several cycles before the corresponding branches are executed in a deeply pipelined processor, such a linked stack mechanism helps implement the instruction fetching scheme across subroutine calls and returns to a great extent. Notwithstanding, the link stack can become corrupted during the process of speculative instruction fetching and execution.
Consider, for example, the case where a subroutine call is performed using a xe2x80x9cbranch and link instructionxe2x80x9d and a return from subroutine is achieved using a xe2x80x9cbranch to link registerxe2x80x9d or xe2x80x9cbclrxe2x80x9d instruction. It may happen that a xe2x80x9cbclrxe2x80x9d instruction, which for example returns to a location xe2x80x9cAxe2x80x9d, is fetched speculatively followed by a speculative fetch of a xe2x80x9cbranch and linkxe2x80x9d instruction, for example from call-site B. The link stack is updated at fetch time, such that after these instructions are fetched, the address location xe2x80x9cAxe2x80x9d is replaced by the address location xe2x80x9cB+4xe2x80x9d (each instruction consists of four bytes) at the top of the link stack. Since both the xe2x80x9cbclrxe2x80x9d and xe2x80x9cbranch and linkxe2x80x9d instructions are speculatively fetched, they may not ultimately be in the actual execution path. If these instructions are not in fact in the actual execution path, (in which case the instructions are flushed out), the link stack becomes corrupted.
Generally, any time one or more xe2x80x9cbclrxe2x80x9d instructions are followed by one or more xe2x80x9cbranch and linkxe2x80x9d instructions in the speculated path, the link stack becomes corrupted if the speculation turns out to be wrong. For a commercial programming workload, about 2% of the instructions are xe2x80x9cbclrxe2x80x9d instructions and therefore it becomes very important to be able to predict the target address for these instructions with a good degree of accuracy in deeply pipelined machines. Thus, the need has arisen for circuits, systems and methods to control link stack corruption, as well as to recover a link stack from corrupted condition.
The principles of the present invention are embodied in circuits, systems and methods for executing branch instructions. In accordance to one embodiment of these principles, instruction branching circuitry is disclosed which includes a plurality of logical stacks each having a plurality of entries for storing an address to a corresponding instruction in memory. A counter generates a pointer to an entry of an active one of the logical stacks, the counter including incrementation logic incrementing a stored pointer value following a Push operation and decrementation logic decrementing the stored pointer value following a Pop operation to the active logical stacks. Selector circuitry selects the active one of the logical stacks in accordance with the performance of the Push and Pop operations.
According to one specific embodiment of the inventive principles, the selector circuitry changes the active stack from a first stack to a second stack in response to a Pop operation followed by an instruction for a Push operation, the Push operation then performed to the second stack. In a second particular embodiment, the selector circuitry changes the active stack in response to the state of a bit associated with information popped from the active stack during a Pop operation.
The principles of the present invention provide substantial advantages over the prior art. Among other things, circuitry and methods are provided which allow for the control of link stack corruption. In particular, the present inventive principles allow for the construction and operation of a register file of m-logically separate stacks which allows recovery of mxe2x88x921 number of redirections caused by misspeculation during the execution of branching instructions.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention.